package com.acme.BufferHashMap;

import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.IntBuffer;

/**
 * @author Artem Kalchenko
 *
 */
public class BufferHashMap {
	private final int EMPTY_CELL_INDICATOR = -2;
	private final int EMPTY_NEXT_INDICATOR = -1;

	private IntBuffer buff;

	private int bucketsNumber = 10;
	private final int capacity;
	private int size;
	
	private int emptyListHead = 0;
	
	public BufferHashMap(ByteBuffer buff) {
		this.buff = buff.asIntBuffer();
		capacity = this.buff.capacity()/3;
		bucketsNumber = capacity/10;
		clear();
	}

	/**
	 * Removes all of the mappings from this map. The map will be empty after this call returns.
	 */
	public void clear() {
		for (int i=1; i < capacity; i++) {
			this.buff.put(i*3-1, EMPTY_CELL_INDICATOR);
		}
		size = 0;
		emptyListHead = bucketsNumber;
		for (int i=emptyListHead; i < capacity-1; i++) {
			setNext(i, i+1);
		}
		setNext(capacity - 1, EMPTY_NEXT_INDICATOR);
	}
	
	/**
	 * Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
	 * 
	 * @param key key with which the specified value is to be associated
	 * @param value value to be associated with the specified key
	 * @return the previous value associated with key, or null if there was no mapping for key
	 * @throws NotEnoughMemoryException
	 */
	public Integer put(int key, int value) throws NotEnoughMemoryException {
		if (size >= capacity) {
			throw new NotEnoughMemoryException();
		}
		
		int index = hash(key);
		int newIndex = 0;
		int prevValue = 0;
		
		if (getNext(index) == EMPTY_CELL_INDICATOR) {
			setElement(index, key, value, EMPTY_NEXT_INDICATOR);
		} else {
			while (getNext(index) != EMPTY_NEXT_INDICATOR) {
				if (key == getKey(index)) {
					prevValue = getValue(index);
					setValue(index,value);
					return prevValue;
				}
				index = getNext(index);
			}
			if ((newIndex = getFreeSpaceIndex()) == -1) 
				throw new NotEnoughMemoryException();
			setElement(newIndex, key, value, EMPTY_NEXT_INDICATOR);
			setNext(index, newIndex);
		}
		size++;
		return null;
	}

	/**
	 * Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
	 * 
	 * @param key the key whose associated value is to be returned
	 * @return the value to which the specified key is mapped, or null if this map contains no mapping for the key
	 */
	public Integer get(int key) { 
		int index = hash(key);
		while ((getKey(index) != key) && (getNext(index) != EMPTY_NEXT_INDICATOR)) {
			index = getNext(index);
		}
		return (getKey(index) == key && getNext(index) != EMPTY_CELL_INDICATOR) ? getValue(index) : null;
	}
	
	/**
	 * Removes the mapping for the specified key from this map if present.
	 * 
	 * @param key key whose mapping is to be removed from the map
	 * @return the previous value associated with key, or null if there was no mapping for key.
	 */
	public Integer remove(int key) {
		int index = hash(key);
		int prevIndex = index;
		if (getKey(index) == key) {
			int value = getValue(index);
			int nextInChainIndex = 0;
			if ((nextInChainIndex = getNext(index)) != EMPTY_NEXT_INDICATOR) {
				setElement(index, getKey(nextInChainIndex), getValue(nextInChainIndex), getNext(nextInChainIndex));
				addFreeSpaceIndex(nextInChainIndex);
			} else {
				setNext(index, EMPTY_CELL_INDICATOR);
			}
			size--;
			return value;
		}
		
		while ((getKey(index) != key) && (getNext(index) != EMPTY_NEXT_INDICATOR)) {
			prevIndex = index;
			index = getNext(index);
		}
		
		if (getKey(index) != key) {
			return null;
		}
		
		setNext(prevIndex, getNext(index));
		addFreeSpaceIndex(index);
		size--;
		return getValue(index);
	}
	
	/**
     * Returns true if this map contains a mapping for the specified key.
     *
     * @param key The key whose presence in this map is to be tested
     * @return true if this map contains a mapping for the specified key.
     */
	public boolean containsKey(int key) {
        return get(key) != null;
    }
	
    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
	public int size() {
		return size;
	}
	
	public void printBuff() {
		for (int i=0; i < capacity; i++) {
			System.out.printf("%d\t%d\t%d\t%d\n", i, getKey(i), getValue(i), getNext(i));
		}
	}
	
	private void setElement(int index, int key, int value, int next) {
		setKey(index, key);
		setValue(index, value);
		setNext(index, next);
	}
	
	private void setKey(int index, int key){
		buff.put(3*index, key);
	}
	private void setValue(int index, int value){
		buff.put(3*index+1, value);
	}
	private void setNext(int index, int next){
		buff.put(3*index+2, next);
	}
	private int getKey(int index){
		return buff.get(3*index);
	}
	private int getValue(int index){
		return buff.get(3*index+1);
	}
	private int getNext(int index){
		return buff.get(3*index+2);
	}
	
	private int getFreeSpaceIndex() {
		int free = emptyListHead;
		if (emptyListHead != -1) {
			emptyListHead = getNext(emptyListHead);
		}
		return free;
	}
	
	private void addFreeSpaceIndex (int index) {
		setNext(index, emptyListHead);
		emptyListHead = index;
	}
	
	private int hash(int key) {
		key += (key << 12);
        key ^= (key >> 22); 
        key += (key << 4); 
        key ^= (key >> 9); 
        key += (key << 10); 
        key ^= (key >> 2); 
        key += (key << 7);
        key ^= (key >> 12); 
		return key % bucketsNumber;
	}

}
